package Matrix.Medium;

import java.util.HashSet;

public class LC0073 {
    /**
     * 记录空行和空列号，O(m+n)空间复杂度
     */
    public void setZeroes(int[][] matrix) {
        HashSet<Integer> zeroRows = new HashSet<>();
        HashSet<Integer> zeroCols = new HashSet<>();
        int M = matrix.length;
        int N = matrix[0].length;
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                if (matrix[i][j] == 0) {
                    zeroRows.add(i);
                    zeroCols.add(j);
                }
            }
        }

        for (int row : zeroRows) {
            for (int j = 0; j < N; j++)
                matrix[row][j] = 0;
        }
        for (int col : zeroCols) {
            for (int i = 0; i < M; i++)
                matrix[i][col] = 0;
        }
    }

    /**
     * 常量空间算法。将每行/每列的第1个元素，作为该行/该列置0的标志。第0行/第0列本身是否置零，用额外的两个标志位判断。
     * 这道题目的启发是，如果题目要求常量空间，可以考虑利用传入的数据结构本身来做一些存储。
     */
    public void setZeroesConstantSpace(int[][] matrix) {
        boolean firstRowFlag = false, firstColFlag = false; // 第0行和第0列是否需要置0
        int M = matrix.length;
        int N = matrix[0].length;
        // 设置首行首列标记
        for (int j = 0; j < N; j++) {
            if (matrix[0][j] == 0) {
                firstRowFlag = true;
            }
        }
        for (int i = 0; i < M; i++) {
            if (matrix[i][0] == 0) {
                firstColFlag = true;
                break;
            }
        }

        // 设置各行各列标记
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }

        // 元素置零
        for (int i = 1; i < M; i++) {
            if (matrix[i][0] == 0) {
                for (int j = 1; j < N; j++) matrix[i][j] = 0;
            }
        }
        for (int j = 1; j < N; j++) {
            if (matrix[0][j] == 0) {
                for (int i = 1; i < M; i++) matrix[i][j] = 0;
            }
        }

        if (firstRowFlag) {
            for (int j = 0; j < N; j++) matrix[0][j] = 0;
        }
        if (firstColFlag) {
            for (int i = 0; i < M; i++) matrix[i][0] = 0;
        }
    }
}
